/*
150. 逆波兰表达式求值

求在 逆波兰表示法 中算术表达式的值。

有效的运算符号包括 +, -, *, / 。每个运算对象可以是整数，也可以是另一个逆波兰计数表达。

例如：

  ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
  ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6
*/

class Solution
{
private:
    enum {
        NUMBER,
        OP_ADD,
        OP_SUB,
        OP_DIV,
        OP_MUL,
        INVALID
    };
    int getType(const string &s, int &number)
    {
        int op = INVALID;
        number = 0;
        if(s.size() == 1) {
            switch(s[0]) {
            case '+':
                op = OP_ADD;
                break;
            case '-':
                op = OP_SUB;
                break;
            case '*':
                op = OP_MUL;
                break;
            case '/':
                op = OP_DIV;
                break;
            case '0':
            case '1':
            case '2':
            case '3':
            case '4':
            case '5':
            case '6':
            case '7':
            case '8':
            case '9':
                number = s[0] - '0';
                op = NUMBER;
                break;
            default:
                break;
            }
        } else if(s.size() > 0) {
            bool minus = false;
            for(int i = 0; i < s.size(); i++) {
                char ch = s[i];
                switch(ch) {
                case '0':
                case '1':
                case '2':
                case '3':
                case '4':
                case '5':
                case '6':
                case '7':
                case '8':
                case '9':
                    number = number * 10 + (ch - '0');
                    break;
                case '-':
                    if(!minus && 0 == i)
                        minus = true;
                    else
                        return INVALID;
                    break;
                default:
                    return INVALID;
                }
            }
            if(minus) number = 0 - number;
            op = NUMBER;
        }
        return op;
    }

public:
    int evalRPN(vector<string> &tokens)
    {
        vector<int> stk(tokens.size());
        int         stk_count = 0;
        for(int i = 0; i < tokens.size(); i++) {
            int num = 0;
            switch(getType(tokens[i], num)) {
            case NUMBER:
                stk[stk_count++] = num;
                break;
            case OP_ADD:
                if(stk_count < 2) return 0;
                stk_count--;
                stk[stk_count - 1] += stk[stk_count];
                break;
            case OP_SUB:
                if(stk_count < 2) return 0;
                stk_count--;
                stk[stk_count - 1] -= stk[stk_count];
                break;
            case OP_DIV:
                if(stk_count < 2 || stk[stk_count - 1] == 0) return 0;
                stk_count--;
                stk[stk_count - 1] /= stk[stk_count];
                break;
            case OP_MUL:
                if(stk_count < 2) return 0;
                stk_count--;
                stk[stk_count - 1] *= stk[stk_count];
                break;
            default:
                return 0;
            }
        }
        if(stk_count != 1) return 0;
        return stk[0];
    }
};